package erChaShuFuXi;

import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class erChaShuXunLianTi {
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
}

//判断俩个节点是否一样

    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p==null&&q==null){
            return false;
        }
        if(p!=null&&p==null){
            return false;
        }
        if(p==null&&p!=null){
            return false;
        }
        isSameTree(p.left,q.left);
        isSameTree(p.right,q.right);
        return true;
    }

//判断另一棵树的节点

    public boolean issameTree(TreeNode root,TreeNode subRoot){
        if(root==null&&subRoot==null){
            return true;
        }
        if((root==null&&subRoot!=null)||(root!=null&&subRoot==null)){
            return false;
        }
        if(root.val!=subRoot.val){
            return false;
        }
        return issameTree(root.left,subRoot.left)&&
                issameTree(root.right,subRoot.right);
}
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if (root == null) {
            return false;
        }
        if (issameTree(root, subRoot)) return true;
        if (isSubtree(root.left, subRoot)) return true;
        if (isSubtree(root.right, subRoot)) return true;
        return false;
    }

//翻转二叉树
    public TreeNode invertTree(TreeNode root) {
        if(root==null){
            return null;
        }
        TreeNode cur=root.left;
        root.left=root.right;
        root.right=cur;
        //记住就是每个节点都是要调换位置，原来的节点已经调换了位置
        invertTree(root.left);
        invertTree(root.right);
        return root;
    }

//判断一棵树是否是平衡树 首先计算出树的高度，只要有一边的高度高于另一边俩层
    public int getHeight(TreeNode root) {
        if(root==null){
            return 0;
        }
        int leftheight=getHeight(root.left);
        int rightheight=getHeight(root.right);

        return leftheight>rightheight?leftheight+1:rightheight+1;
    }
    public boolean isBalanced(TreeNode root) {
        if (root==null){
            return true;
        }
        int leftheight=getHeight(root.left);
        int rightheight=getHeight(root.right);
        return Math.abs(leftheight-rightheight)<2
                &&isBalanced(root.left)
                &&isBalanced(root.right);

    }
}


